package com.sakura.动态规划;

public class Code63_不同路径II {
    public static void main(String[] args) {
        int[][] obstacleGrid = {
                {0, 0, 0},
                {0, 1, 0},
                {0, 0, 0}
        };
        System.out.println(uniquePathsWithObstacles(obstacleGrid));

        obstacleGrid = new int[][]{
                {0, 1},
                {0, 0}
        };
        System.out.println(uniquePathsWithObstacles(obstacleGrid));
    }

    public static int uniquePathsWithObstacles(int[][] obstacleGrid) {
        // 特判，如果grid中启动为障碍物时直接返回 0
        if (obstacleGrid[0][0] == 1) {
            return 0;
        }
        int n = obstacleGrid.length;
        int m = obstacleGrid[0].length;
        int[][] dp = new int[n][m];
        dp[n - 1][m - 1] = 1; // 终点位置

        // 行处理
        for (int i = n - 2; i >= 0; i--) {
            // 判断当前行的下一行是否为 障碍物
            if (obstacleGrid[i + 1][m - 1] == 1 || obstacleGrid[i][m - 1] == 1) {
                // 如果是障碍物，则当前位置为 0
                dp[i][m - 1] = 0;
                continue;
            }
            dp[i][m - 1] = dp[i + 1][m - 1];
        }
        // 列处理
        for (int j = m - 2; j >= 0; j--) {
            if (obstacleGrid[n - 1][j + 1] == 1 || obstacleGrid[n - 1][j] == 1) {
                dp[n - 1][j] = 0;
                continue;
            }
            dp[n - 1][j] = dp[n - 1][j + 1];
        }

        //  填表
        for (int i = n - 2; i >= 0; i--) {
            for (int j = m - 2; j >= 0; j--) {
                if (obstacleGrid[i][j] == 1) {
                    dp[i][j] = 0;
                    continue;
                }
                dp[i][j] = dp[i + 1][j] + dp[i][j + 1];
            }
        }
        return dp[0][0];
    }
}
